<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/%E6%AD%A6%E6%B1%8932x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/%E6%AD%A6%E6%B1%8916x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib1/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib1/pace/pace-theme-center-simple.min.css">
  <script src="/lib1/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"example.com","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="二叉搜索树的操作集锦总路线⼆叉树算法的设计的总路线：明确⼀个节点要做的事情，然后剩下的事抛给 框架。 123456void traverse(TreeNode root) &amp;#123;     &#x2F;&#x2F; root 需要做什么？在这做。     &#x2F;&#x2F; 其他的不⽤ root 操⼼，抛给框架     traverse(root.left);     traverse(root.right); &amp;#125;">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构算法">
<meta property="og:url" content="http://example.com/2020/10/08/%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="Technological Blog">
<meta property="og:description" content="二叉搜索树的操作集锦总路线⼆叉树算法的设计的总路线：明确⼀个节点要做的事情，然后剩下的事抛给 框架。 123456void traverse(TreeNode root) &amp;#123;     &#x2F;&#x2F; root 需要做什么？在这做。     &#x2F;&#x2F; 其他的不⽤ root 操⼼，抛给框架     traverse(root.left);     traverse(root.right); &amp;#125;">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://example.com/image/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E5%A0%86.png">
<meta property="article:published_time" content="2020-10-08T11:42:38.000Z">
<meta property="article:modified_time" content="2021-11-03T08:29:55.343Z">
<meta property="article:author" content="Li Yudong">
<meta property="article:tag" content="算法框架">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://example.com/image/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E5%A0%86.png">

<link rel="canonical" href="http://example.com/2020/10/08/%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>数据结构算法 | Technological Blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Technological Blog</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">IT小白的成长之旅</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签<span class="badge">18</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="th fa-fw"></i>分类<span class="badge">14</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档<span class="badge">95</span></a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

  <a href="https://github.com/tiarmor1" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://example.com/2020/10/08/%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/author.jpg">
      <meta itemprop="name" content="Li Yudong">
      <meta itemprop="description" content="">
    </span>
    
    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Technological Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数据结构算法
        </h1>
    
        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
    
              <time title="创建时间：2020-10-08 19:42:38" itemprop="dateCreated datePublished" datetime="2020-10-08T19:42:38+08:00">2020-10-08</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-11-03 16:29:55" itemprop="dateModified" datetime="2021-11-03T16:29:55+08:00">2021-11-03</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
                </span>
            </span>
    
          
    
        </div>
      </header>
    
    
    
    
    <div class="post-body" itemprop="articleBody">
    
      
        <h1 id="二叉搜索树的操作集锦"><a href="#二叉搜索树的操作集锦" class="headerlink" title="二叉搜索树的操作集锦"></a>二叉搜索树的操作集锦</h1><h2 id="总路线"><a href="#总路线" class="headerlink" title="总路线"></a>总路线</h2><p>⼆叉树算法的设计的总路线：明确⼀个节点要做的事情，然后剩下的事抛给 框架。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">traverse</span><span class="params">(TreeNode root)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// root 需要做什么？在这做。 </span></span><br><span class="line">    <span class="comment">// 其他的不⽤ root 操⼼，抛给框架 </span></span><br><span class="line">    traverse(root.left); </span><br><span class="line">    traverse(root.right); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="如何把⼆叉树所有的节点中的值加⼀？"><a href="#如何把⼆叉树所有的节点中的值加⼀？" class="headerlink" title="如何把⼆叉树所有的节点中的值加⼀？"></a><strong>如何把⼆叉树所有的节点中的值加⼀？</strong></h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">plusOne</span><span class="params">(TreeNode root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span>; </span><br><span class="line">    root.val += <span class="number">1</span>; </span><br><span class="line">    plusOne(root.left); </span><br><span class="line">    plusOne(root.right); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="如何判断两棵⼆叉树是否完全相同？"><a href="#如何判断两棵⼆叉树是否完全相同？" class="headerlink" title="如何判断两棵⼆叉树是否完全相同？"></a><strong>如何判断两棵⼆叉树是否完全相同？</strong></h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isSameTree</span><span class="params">(TreeNode root1, TreeNode root2)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// 都为空的话，显然相同 </span></span><br><span class="line">    <span class="keyword">if</span> (root1 == null &amp;&amp; root2 == null) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="comment">// ⼀个为空，⼀个⾮空，显然不同 </span></span><br><span class="line">    <span class="keyword">if</span> (root1 == null || root2 == null) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="comment">// 两个都⾮空，但 val 不⼀样也不⾏ </span></span><br><span class="line">    <span class="keyword">if</span> (root1.val != root2.val) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="comment">// root1 和 root2 该⽐的都⽐完了 </span></span><br><span class="line">    <span class="keyword">return</span> isSameTree(root1.left, root2.left) </span><br><span class="line">        &amp;&amp; isSameTree(root1.right, root2.right); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>借助框架可以理解上述两个例子，那么就能解决所有二叉树算法。</p>
<p>二叉搜索树BST是一种很常用的二叉树，定义为：一个二叉树中，任意节点的值要大于等于左子树所有节点的值，且要小于等于右边子树所有节点的值。</p>
<p>基础操作有：判断合法性、增、删、查。</p>
<h2 id="判断BST的合法性"><a href="#判断BST的合法性" class="headerlink" title="判断BST的合法性"></a>判断BST的合法性</h2><p>这⾥是有坑的哦，我们按照刚才的思路，每个节点⾃⼰要做的事不就是⽐较 ⾃⼰和左右孩⼦吗？看起来应该这样写代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isValidBST</span><span class="params">(TreeNode root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    <span class="keyword">if</span> (root.left != null &amp;&amp; root.val &lt;= root.left.val) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">if</span> (root.right != null &amp;&amp; root.val &gt;= root.right.val) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">return</span> isValidBST(root.left) </span><br><span class="line">        &amp;&amp; isValidBST(root.right); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>但是这个算法出现了错误，BST 的每个节点应该要⼩于右边⼦树的所有节 点，下⾯这个⼆叉树显然不是 BST，但是我们的算法会把它判定为 BST。出现错误，不要慌张，框架没有错，⼀定是某个细节问题没注意到。我们重 新看⼀下 BST 的定义，root 需要做的不只是和左右⼦节点⽐较，⽽是要整 个左⼦树和右⼦树所有节点⽐较。怎么办，鞭⻓莫及啊！</p>
<p>这种情况，我们可以使⽤辅助函数，增加函数参数列表，在参数中携带额外 信息，请看正确的代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isValidBST</span><span class="params">(TreeNode root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">return</span> isValidBST(root, null, null); </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isValidBST</span><span class="params">(TreeNode root, TreeNode <span class="built_in">min</span>, TreeNode <span class="built_in">max</span>)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">min</span> != null &amp;&amp; root.val &lt;= <span class="built_in">min</span>.val) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">max</span> != null &amp;&amp; root.val &gt;= <span class="built_in">max</span>.val) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">return</span> isValidBST(root.left, <span class="built_in">min</span>, root) </span><br><span class="line">        &amp;&amp; isValidBST(root.right, root, <span class="built_in">max</span>); &#125;</span><br></pre></td></tr></table></figure>

<h2 id="在BST中查找一个数是否存在"><a href="#在BST中查找一个数是否存在" class="headerlink" title="在BST中查找一个数是否存在"></a>在BST中查找一个数是否存在</h2><p>根据我们的指导思想，可以这样写代码： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isInBST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">if</span> (root.val == target) <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> isInBST(root.left, target) || </span><br><span class="line">        isInBST(root.right, target); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这样写完全正确，充分证明了你的框架性思维已经养成。现在你可以考虑⼀ 点细节问题了：如何充分利⽤信息，把 BST 这个“左⼩右⼤”的特性⽤上？ 很简单，其实不需要递归地搜索两边，类似⼆分查找思想，根据 target 和 root.val 的⼤⼩⽐较，就能排除⼀边。我们把上⾯的思路稍稍改动：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isInBST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    <span class="keyword">if</span> (root.val == target) </span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; target) </span><br><span class="line">        <span class="keyword">return</span> isInBST(root.right, target);</span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; target) </span><br><span class="line">        <span class="keyword">return</span> isInBST(root.left, target); </span><br><span class="line">    <span class="comment">// root 该做的事做完了，顺带把框架也完成了，妙 </span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>于是，我们对原始框架进⾏改造，抽象出⼀套<strong>针对</strong> <strong>BST</strong> <strong>的遍历框架</strong>：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">BST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root.val == target) </span><br><span class="line">        <span class="comment">// 找到⽬标，做点什么 </span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; target) </span><br><span class="line">            BST(root.right, target);</span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; target) </span><br><span class="line">            BST(root.left, target); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="在-BST-中插⼊⼀个数"><a href="#在-BST-中插⼊⼀个数" class="headerlink" title="在 BST 中插⼊⼀个数"></a><strong>在</strong> <strong>BST</strong> <strong>中插⼊⼀个数</strong></h2><p>对数据结构的操作⽆⾮遍历 + 访问，遍历就是“找”，访问就是“改”。具体到 这个问题，插⼊⼀个数，就是先找到插⼊位置，然后进⾏插⼊操作。 </p>
<p>上⼀个问题，我们总结了 BST 中的遍历框架，就是“找”的问题。直接套框 架，加上“改”的操作即可。⼀旦涉及“改”，函数就要返回 TreeNode 类型， 并且对递归调⽤的返回值进⾏接收。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode <span class="title">insertIntoBST</span><span class="params">(TreeNode root, <span class="keyword">int</span> val)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// 找到空位置插⼊新节点 </span></span><br><span class="line">    <span class="keyword">if</span> (root == null) </span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(val); </span><br><span class="line">    <span class="comment">// if (root.val == val) </span></span><br><span class="line">    <span class="comment">// BST 中⼀般不会插⼊已存在元素 </span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; val) </span><br><span class="line">        root.right = insertIntoBST(root.right, val); </span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; val) </span><br><span class="line">        root.left = insertIntoBST(root.left, val); </span><br><span class="line">    <span class="keyword">return</span> root; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="在-BST-中删除⼀个数"><a href="#在-BST-中删除⼀个数" class="headerlink" title="在 BST 中删除⼀个数"></a><strong>在</strong> <strong>BST</strong> <strong>中删除⼀个数</strong></h2><p>这个问题稍微复杂，不过你有框架指导，难不住你。跟插⼊操作类似， 先“找”再“改”，先把框架写出来再说： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode <span class="title">deleteNode</span><span class="params">(TreeNode root, <span class="keyword">int</span> key)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root.val == key) &#123; </span><br><span class="line">        <span class="comment">// 找到啦，进⾏删除 </span></span><br><span class="line">    &#125; </span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (root.val &gt; key) &#123; </span><br><span class="line">        root.left = deleteNode(root.left, key); </span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (root.val &lt; key) &#123; </span><br><span class="line">        root.right = deleteNode(root.right, key); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>找到⽬标节点了，⽐⽅说是节点 A，如何删除这个节点，这是难点。因为删 除节点的同时不能破坏 BST 的性质。有三种情况，⽤图⽚来说明。 </p>
<p>情况 1：A 恰好是末端节点，两个⼦节点都为空，那么它可以当场去世了。 </p>
<p>情况 2：A 只有⼀个⾮空⼦节点，那么它要让这个孩⼦接替⾃⼰的位置。</p>
<p>情况 3：A 有两个⼦节点，⿇烦了，为了不破坏 BST 的性质，A 必须找到 左⼦树中最⼤的那个节点，或者右⼦树中最⼩的那个节点来接替⾃⼰。我们 以第⼆种⽅式讲解。 </p>
<p>三种情况分析完毕，填⼊框架，简化⼀下代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode <span class="title">deleteNode</span><span class="params">(TreeNode root, <span class="keyword">int</span> key)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> null; </span><br><span class="line">    <span class="keyword">if</span> (root.val == key) &#123; </span><br><span class="line">        <span class="comment">// 这两个 if 把情况 1 和 2 都正确处理了 </span></span><br><span class="line">        <span class="keyword">if</span> (root.left == null) <span class="keyword">return</span> root.right; </span><br><span class="line">        <span class="keyword">if</span> (root.right == null) <span class="keyword">return</span> root.left; </span><br><span class="line">        <span class="comment">// 处理情况 3 </span></span><br><span class="line">        TreeNode minNode = getMin(root.right); </span><br><span class="line">        root.val = minNode.val; </span><br><span class="line">        root.right = deleteNode(root.right, minNode.val); </span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (root.val &gt; key) &#123; </span><br><span class="line">        root.left = deleteNode(root.left, key); </span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (root.val &lt; key) &#123; </span><br><span class="line">        root.right = deleteNode(root.right, key); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root; </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function">TreeNode <span class="title">getMin</span><span class="params">(TreeNode node)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// BST 最左边的就是最⼩的 </span></span><br><span class="line">    <span class="keyword">while</span> (node.left != null) node = node.left; </span><br><span class="line">    <span class="keyword">return</span> node; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>删除操作就完成了。注意⼀下，这个删除操作并不完美，因为我们⼀般不会 通过 root.val = minNode.val 修改节点内部的值来交换节点，⽽是通过⼀系列 略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应⽤中，val 域可能会很⼤，修改起来很耗时，⽽链表操作⽆⾮改⼀改指针，⽽不会去碰 内部数据。 </p>
<p>但这⾥忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层 细化问题的思维⽅式。 </p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>通过这篇⽂章，你学会了如下⼏个技巧： </p>
<p>1、⼆叉树算法设计的总路线：把当前节点要做的事做好，其他的交给递归 </p>
<p>框架，不⽤当前节点操⼼。 </p>
<p>2、如果当前节点会对下⾯的⼦节点有整体影响，可以通过辅助函数增⻓参 </p>
<p>数列表，借助参数传递信息。 </p>
<p>3、在⼆叉树框架之上，扩展出⼀套 BST 遍历框架：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">BST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (root.val == target) ;</span><br><span class="line">        <span class="comment">// 找到⽬标，做点什么 </span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; target) </span><br><span class="line">            BST(root.right, target); </span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; target) </span><br><span class="line">        BST(root.left, target); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>4、掌握了 BST 的基本操作。</p>
<h1 id="快速计算完全⼆叉树的节点"><a href="#快速计算完全⼆叉树的节点" class="headerlink" title="快速计算完全⼆叉树的节点"></a>快速计算完全⼆叉树的节点</h1><p>如果让你数⼀下⼀棵普通⼆叉树有多少个节点，这很简单，只要在⼆叉树的 遍历框架上加⼀点代码就⾏了。 </p>
<p>但是，如果给你⼀棵完全⼆叉树，让你计算它的节点个数，你会不会？算法 的时间复杂度是多少？这个算法的时间复杂度应该是 O(logN*logN)，如果 你⼼中的算法没有达到⾼效，那么本⽂就是给你写的。 </p>
<p>⾸先要明确⼀下两个关于⼆叉树的名词「完全⼆叉树」和「满⼆叉树」。 我们说的<strong>完全⼆叉树</strong>如下图，每⼀层都是紧凑靠左排列的： 我们说的<strong>满⼆叉树</strong>如下图，是⼀种特殊的完全⼆叉树，每层都是是满的，像 ⼀个稳定的三⾓形： </p>
<h2 id="具体方法"><a href="#具体方法" class="headerlink" title="具体方法"></a>具体方法</h2><p>如果是一个<strong>普通</strong>二叉树，显然只要向下面这样遍历一边即可，时间复杂度 O(N)：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">countNodes</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span> + countNodes(root.left) + countNodes(root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>那如果是一棵<strong>满</strong>二叉树，节点总数就和树的高度呈指数关系，时间复杂度 O(logN)：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">countNodes</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> h = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 计算树的高度</span></span><br><span class="line">    <span class="keyword">while</span> (root != null) &#123;</span><br><span class="line">        root = root.left;</span><br><span class="line">        h++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 节点总数就是 2^h - 1</span></span><br><span class="line">    <span class="keyword">return</span> (<span class="keyword">int</span>)Math.<span class="built_in">pow</span>(<span class="number">2</span>, h) - <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>完全</strong>二叉树比普通二叉树特殊，但又没有满二叉树那么特殊，计算它的节点总数，可以说是普通二叉树和完全二叉树的结合版，先看代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">countNodes</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">    TreeNode l = root, r = root;</span><br><span class="line">    <span class="comment">// 记录左、右子树的高度</span></span><br><span class="line">    <span class="keyword">int</span> hl = <span class="number">0</span>, hr = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (l != null) &#123;</span><br><span class="line">        l = l.left;</span><br><span class="line">        hl++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (r != null) &#123;</span><br><span class="line">        r = r.right;</span><br><span class="line">        hr++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果左右子树的高度相同，则是一棵满二叉树</span></span><br><span class="line">    <span class="keyword">if</span> (hl == hr) &#123;</span><br><span class="line">        <span class="keyword">return</span> (<span class="keyword">int</span>)Math.<span class="built_in">pow</span>(<span class="number">2</span>, hl) - <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果左右高度不同，则按照普通二叉树的逻辑计算</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span> + countNodes(root.left) + countNodes(root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>结合刚才针对满二叉树和普通二叉树的算法，上面这段代码应该不难理解，就是一个结合版，但是<strong>其中降低时间复杂度的技巧是非常微妙的</strong>。</p>
<h2 id="复杂度分析"><a href="#复杂度分析" class="headerlink" title="复杂度分析"></a>复杂度分析</h2><p>开头说了，这个算法的时间复杂度是 O(logN<em>logN)，这是怎么算出来的呢？直觉感觉好像最坏情况下是 O(N</em>logN) 吧，因为之前的 while 需要 logN 的时间，最后要 O(N) 的时间向左右子树递归：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">return</span> <span class="number">1</span> + countNodes(root.left) + countNodes(root.right);</span><br></pre></td></tr></table></figure>

<p><strong>关键点在于，这两个递归只有一个会真的递归下去，另一个一定会触发<code>hl == hr</code>而立即返回，不会递归下去</strong>。</p>
<p>为什么呢？原因如下：</p>
<p><strong>一棵完全二叉树的两棵子树，至少有一棵是满二叉树</strong>：</p>
<p>看图就明显了吧，由于完全二叉树的性质，其子树一定有一棵是满的，所以一定会触发<code>hl == hr</code>，只消耗 O(logN) 的复杂度而不会继续递归。</p>
<p>综上，算法的递归深度就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。所以说，「完全二叉树」这个概念还是有它存在的原因的，不仅适用于数组实现二叉堆，而且连计算节点总数这种看起来简单的操作都有高效的算法实现。</p>
<h1 id="如何使用单调栈解题"><a href="#如何使用单调栈解题" class="headerlink" title="如何使用单调栈解题"></a>如何使用单调栈解题</h1><p>单调栈实际上就是栈，只是利⽤了⼀些巧妙的逻辑，使得每次新元素⼊栈 后，栈内的元素都保持有序（单调递增或单调递减）。听起来有点像堆（heap）？不是的，单调栈⽤途不太⼴泛，只处理⼀种典型 的问题，叫做 Next Greater Element。本⽂⽤讲解单调队列的算法模版解决 这类问题，并且探讨处理「循环数组」的策略。 </p>
<h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><p>⾸先，讲解 Next Greater Number 的原始问题：给你⼀个数组，返回⼀个等 ⻓的数组，对应索引存储着下⼀个更⼤元素，如果没有更⼤的元素，就存 -1。不好⽤语⾔解释清楚，直接上⼀个例⼦： </p>
<p>给你⼀个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。 </p>
<p>解释：第⼀个 2 后⾯⽐ 2 ⼤的数是 4; 1 后⾯⽐ 1 ⼤的数是 2；第⼆个 2 后⾯ ⽐ 2 ⼤的数是 4; 4 后⾯没有⽐ 4 ⼤的数，填 -1；3 后⾯没有⽐ 3 ⼤的数，填 -1。这道题的暴⼒解法很好想到，就是对每个元素后⾯都进⾏扫描，找到第⼀个 更⼤的元素就⾏了。但是暴⼒解法的时间复杂度是 O(n^2)。 </p>
<h2 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h2><p>这个问题可以这样抽象思考：把数组的元素想象成并列站⽴的⼈，元素⼤⼩ 想象成⼈的⾝⾼。这些⼈⾯对你站成⼀列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后⾯可⻅的第⼀个 ⼈就是「2」的 Next Greater Number，因为⽐「2」⼩的元素⾝⾼不够，都被「2」挡住了，第⼀个露出来的就是答案。 </p>
<p>这个情景很好理解吧？带着这个抽象的情景，先来看下代码</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">nextGreaterElement</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; nums)</span> </span>&#123; </span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">ans</span><span class="params">(nums.<span class="built_in">size</span>())</span></span>; </span><br><span class="line">    <span class="comment">// 存放答案的数组 </span></span><br><span class="line">    <span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; s; </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = nums.<span class="built_in">size</span>() - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123; </span><br><span class="line">        <span class="comment">// 倒着往栈⾥放 </span></span><br><span class="line">        <span class="keyword">while</span> (!s.empty() &amp;&amp; s.top() &lt;= nums[i]) &#123; </span><br><span class="line">            <span class="comment">// 判定个⼦⾼矮 </span></span><br><span class="line">            s.pop(); <span class="comment">// 矮个起开，反正也被挡着了。。。 </span></span><br><span class="line">        &#125;</span><br><span class="line">        ans[i] = s.empty() ? <span class="number">-1</span> : s.top(); <span class="comment">// 这个元素⾝后的第⼀个⾼个 </span></span><br><span class="line">        s.push(nums[i]); </span><br><span class="line">        <span class="comment">// 进队，接受之后的⾝⾼判定吧！ </span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们 借助的是栈的结构，倒着⼊栈，其实是正着出栈。while 循环是把两个“⾼ 个”元素之间的元素排除，因为他们的存在没有意义，前⾯挡着个“更⾼”的 元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。 这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循 环，可能认为这个算法的复杂度也是 O(n^2)，但是实际上这个算法的复杂 度只有 O(n)</p>
<h2 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h2><p>分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push ⼊栈了⼀次，⽽最多会被 pop ⼀次，没有任何冗余操作。所以总的计 算规模是和元素规模 n 成正⽐的，也就是 O(n) 的复杂度。 </p>
<p>给你⼀个数组 T = [73, 74, 75, 71, 69, 72, 76, 73]，这个数组存放的是近⼏天 的天⽓⽓温（这⽓温是铁板烧？不是的，这⾥⽤的华⽒度）。你返回⼀个数 组，计算：对于每⼀天，你还要⾄少等多少天才能等到⼀个更暖和的⽓温； 如果等不到那⼀天，填 0 。</p>
<p>举例：给你 T = [73, 74, 75, 71, 69, 72, 76, 73]，你返回 [1, 1, 4, 2, 1, 1, 0, 0]。 </p>
<p>解释：第⼀天 73 华⽒度，第⼆天 74 华⽒度，⽐ 73 ⼤，所以对于第⼀天， 只要等⼀天就能等到⼀个更暖和的⽓温。后⾯的同理。 你已经对 Next Greater Number 类型问题有些敏感了，这个问题本质上也是 找 Next Greater Number，只不过现在不是问你 Next Greater Number 是多 少，⽽是问你当前距离 Next Greater Number 的距离⽽已。 相同类型的问题，相同的思路，直接调⽤单调栈的算法模板，稍作改动就可 以啦，直接上代码把</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">dailyTemperatures</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; T)</span> </span>&#123; </span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">ans</span><span class="params">(T.<span class="built_in">size</span>())</span></span>; </span><br><span class="line">    <span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; s; <span class="comment">// 这⾥放元素索引，⽽不是元素 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = T.<span class="built_in">size</span>() - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123; </span><br><span class="line">        <span class="keyword">while</span> (!s.empty() &amp;&amp; T[s.top()] &lt;= T[i]) &#123; </span><br><span class="line">            s.pop(); </span><br><span class="line">        &#125;</span><br><span class="line">        ans[i] = s.empty() ? <span class="number">0</span> : (s.top() - i); </span><br><span class="line">        <span class="comment">// 得到索引间距 </span></span><br><span class="line">        s.push(i); </span><br><span class="line">        <span class="comment">// 加⼊索引，⽽不是元素 </span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="扩展问题：循环数组"><a href="#扩展问题：循环数组" class="headerlink" title="扩展问题：循环数组"></a>扩展问题：循环数组</h2><p>单调栈讲解完毕。下⾯开始另⼀个重点：如何处理「循环数组」。 </p>
<p>同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？ </p>
<p>给你⼀个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,4]。拥有了环形属性，最后 ⼀个元素 3 绕了⼀圈后找到了⽐⾃⼰⼤的元素 4 。 </p>
<p>⾸先，计算机的内存都是线性的，没有真正意义上的环形数组，但是我们可 以模拟出环形数组的效果，⼀般是通过 % 运算符求模（余数），获得环形特效</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>&#125;; </span><br><span class="line"><span class="keyword">int</span> n = arr.length, index = <span class="number">0</span>; </span><br><span class="line"><span class="keyword">while</span> (<span class="literal">true</span>) &#123; </span><br><span class="line">    <span class="built_in">print</span>(arr[index % n]); </span><br><span class="line">    index++; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>回到 Next Greater Number 的问题，增加了环形属性后，问题的难点在于： </p>
<p>这个 Next 的意义不仅仅是当前元素的右边了，有可能出现在当前元素的左 边（如上例）。 </p>
<p>明确问题，问题就已经解决了⼀半了。我们可以考虑这样的思路：将原始数 组“翻倍”，就是在后⾯再接⼀个原始数组，这样的话，按照之前“⽐⾝⾼”的 流程，每个元素不仅可以⽐较⾃⼰右边的元素，⽽且也可以和左边的元素⽐ 较了</p>
<p>怎么实现呢？你当然可以把这个双倍⻓度的数组构造出来，然后套⽤算法模 板。但是，我们可以不⽤构造新数组，⽽是利⽤循环数组的技巧来模拟。直 接看代码吧： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">nextGreaterElements</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; nums)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> n = nums.<span class="built_in">size</span>(); </span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">res</span><span class="params">(n)</span></span>; </span><br><span class="line">    <span class="comment">// 存放结果 </span></span><br><span class="line">    <span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; s; </span><br><span class="line">    <span class="comment">// 假装这个数组⻓度翻倍了 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span> * n - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123; </span><br><span class="line">        <span class="keyword">while</span> (!s.empty() &amp;&amp; s.top() &lt;= nums[i % n]) </span><br><span class="line">            s.pop(); </span><br><span class="line">        res[i % n] = s.empty() ? <span class="number">-1</span> : s.top(); </span><br><span class="line">        s.push(nums[i % n]); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="利用单调队列解题"><a href="#利用单调队列解题" class="headerlink" title="利用单调队列解题"></a>利用单调队列解题</h1><p>前⽂讲了⼀种特殊的数据结构「单调栈」monotonic stack，解决了⼀类问题 「Next Greater Number」，本⽂写⼀个类似的数据结构「单调队列」。 也许这种数据结构的名字你没听过，其实没啥难的，就是⼀个「队列」，只 是使⽤了⼀点巧妙的⽅法，使得队列中的元素单调递增（或递减）。这个数 据结构有什么⽤？可以解决滑动窗⼝的⼀系列问题</p>
<h2 id="题目-1"><a href="#题目-1" class="headerlink" title="题目"></a>题目</h2><p>给定一个数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧；你只可以看到在滑动窗口k内的数字，滑动窗口每次只向右移动一位，返回滑动窗口最大值。</p>
<h1 id="二叉堆详解"><a href="#二叉堆详解" class="headerlink" title="二叉堆详解"></a>二叉堆详解</h1><p>⼆叉堆（Binary Heap）没什么神秘，性质⽐⼆叉搜索树 BST 还简单。其主 要操作就两个， sink （下沉）和 swim （上浮），⽤以维护⼆叉堆的性 质。其主要应⽤有两个，⾸先是⼀种排序⽅法「堆排序」，第⼆是⼀种很有 ⽤的数据结构「优先级队列」。 </p>
<p>本⽂就以实现优先级队列（Priority Queue）为例，通过图⽚和⼈类的语⾔来 描述⼀下⼆叉堆怎么运作的</p>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>⼆叉堆其实就是⼀种特殊的⼆叉树（完全⼆叉树），只不过存储在数 组⾥。⼀般的链表⼆叉树，我们操作节点的指针，⽽在数组⾥，我们把数组 索引作为指针： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ⽗节点的索引 </span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">parent</span><span class="params">(<span class="keyword">int</span> root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">return</span> root / <span class="number">2</span>; </span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 左孩⼦的索引 </span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">left</span><span class="params">(<span class="keyword">int</span> root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">return</span> root * <span class="number">2</span>; </span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 右孩⼦的索引 </span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">right</span><span class="params">(<span class="keyword">int</span> root)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">return</span> root * <span class="number">2</span> + <span class="number">1</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>画个图你⽴即就能理解了，注意数组的第⼀个索引 0 空着不⽤</p>
<p><img src="/../../image/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E5%A0%86.png" alt="二叉堆"></p>
<p>PS：因为数组索引是数组，为了⽅便区分，将字符作为数组元素。 </p>
<p>你看到了，把 arr[1] 作为整棵树的根的话，每个节点的⽗节点和左右孩⼦的 索引都可以通过简单的运算得到，这就是⼆叉堆设计的⼀个巧妙之处。为了 ⽅便讲解，下⾯都会画的图都是⼆叉树结构，相信你能把树和数组对应起 来</p>
<p>⼆叉堆还分为最⼤堆和最⼩堆。<strong>最⼤堆的性质是：每个节点都⼤于等于它的</strong> <strong>两个⼦节点。</strong>类似的，最⼩堆的性质是：每个节点都⼩于等于它的⼦节点。 两种堆核⼼思路都是⼀样的，本⽂以最⼤堆为例讲解。 对于⼀个最⼤堆，根据其性质，显然堆顶，也就是 arr[1] ⼀定是所有元素中 最⼤的元素。 </p>
<h2 id="优先级队列"><a href="#优先级队列" class="headerlink" title="优先级队列"></a>优先级队列</h2><p>优先级队列这种数据结构有⼀个很有⽤的功能，你插⼊或者删除元素的时 候，元素会⾃动排序，这底层的原理就是⼆叉堆的操作。 </p>
<p>数据结构的功能⽆⾮增删查该，优先级队列有两个主要 API，分别是 insert 插⼊⼀个元素和 delMax 删除最⼤元素（如果底层⽤最⼩堆，那么 就是 delMin ）。 </p>
<p>下⾯我们实现⼀个简化的优先级队列，先看下代码框架： PS：为了清晰起⻅，这⾥⽤到 Java 的泛型， Key 可以是任何⼀种可⽐较⼤ ⼩的数据类型，你可以认为它是 int、char 等。 </p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MaxPQ</span> </span></span><br><span class="line"><span class="class">    &lt;<span class="title">Key</span> <span class="keyword">extends</span> <span class="title">Comparable</span>&lt;<span class="title">Key</span>&gt;&gt; </span>&#123; </span><br><span class="line">    <span class="comment">// 存储元素的数组 </span></span><br><span class="line">    <span class="keyword">private</span> Key[] pq; </span><br><span class="line">    <span class="comment">// 当前 Priority Queue 中的元素个数 </span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N = <span class="number">0</span>; <span class="function"><span class="keyword">public</span> <span class="title">MaxPQ</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123; </span><br><span class="line">        <span class="comment">// 索引 0 不⽤，所以多分配⼀个空间 </span></span><br><span class="line">        pq = (Key[]) <span class="keyword">new</span> Comparable[cap + <span class="number">1</span>]; </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/* 返回当前队列中最⼤元素 */</span> </span><br><span class="line">    <span class="function"><span class="keyword">public</span> Key <span class="title">max</span><span class="params">()</span> </span>&#123; </span><br><span class="line">        <span class="keyword">return</span> pq[<span class="number">1</span>]; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/* 插⼊元素 e */</span> </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(Key e)</span> </span>&#123;...&#125; </span><br><span class="line">    </span><br><span class="line">    <span class="comment">/* 删除并返回当前队列中最⼤元素 */</span> </span><br><span class="line">    <span class="function"><span class="keyword">public</span> Key <span class="title">delMax</span><span class="params">()</span> </span>&#123;...&#125; </span><br><span class="line">   </span><br><span class="line">    <span class="comment">/* 上浮第 k 个元素，以维护最⼤堆性质 */</span> </span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">swim</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;...&#125; </span><br><span class="line">    </span><br><span class="line">    <span class="comment">/* 下沉第 k 个元素，以维护最⼤堆性质 */</span> </span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">sink</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;...&#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/* 交换数组的两个元素 */</span> </span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">exch</span><span class="params">(<span class="keyword">int</span> i, <span class="keyword">int</span> j)</span> </span>&#123; </span><br><span class="line">        Key temp = pq[i]; </span><br><span class="line">        pq[i] = pq[j]; </span><br><span class="line">        pq[j] = temp; </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/* pq[i] 是否⽐ pq[j] ⼩？ */</span> </span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">less</span><span class="params">(<span class="keyword">int</span> i, <span class="keyword">int</span> j)</span> </span>&#123; </span><br><span class="line">        <span class="keyword">return</span> pq[i].compareTo(pq[j]) &lt; <span class="number">0</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/* 还有 left, right, parent 三个⽅法 */</span> </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>空出来的四个⽅法是⼆叉堆和优先级队列的奥妙所在，下⾯⽤图⽂来逐个理解</p>
<h2 id="swim和sink"><a href="#swim和sink" class="headerlink" title="swim和sink"></a>swim和sink</h2><p>为什么要有上浮 swim 和下沉 sink 的操作呢？为了维护堆结构。 我们要讲的是最⼤堆，每个节点都⽐它的两个⼦节点⼤，但是在插⼊元素和 删除元素时，难免破坏堆的性质，这就需要通过这两个操作来恢复堆的性质了。</p>
<p>对于最⼤堆，会破坏堆性质的有有两种情况： </p>
<p>1、 如果某个节点 A ⽐它的⼦节点（中的⼀个）⼩，那么 A 就不配做⽗节点，应该下去，下⾯那个更⼤的节点上来做⽗节点，这就是对 A 进⾏ <strong>下沉</strong>。 </p>
<p>2、 如果某个节点 A ⽐它的⽗节点⼤，那么 A 不应该做⼦节点，应该把⽗ 节点换下来，⾃⼰去做⽗节点，这就是对 A 的<strong>上浮</strong>。 </p>
<p>当然，错位的节点 A 可能要上浮（或下沉）很多次，才能到达正确的位 置，恢复堆的性质。所以代码中肯定有⼀个 while 循环。 </p>
<p>细⼼的读者也许会问，这两个操作不是互逆吗，所以上浮的操作⼀定能⽤下 沉来完成，为什么我还要费劲写两个⽅法？ 是的，操作是互逆等价的，但是最终我们的操作只会在堆底和堆顶进⾏（等 会讲原因），显然堆底的「错位」元素需要上浮，堆顶的「错位」元素需要 下沉</p>
<p><strong>上浮的代码实现：</strong> </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">swim</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// 如果浮到堆顶，就不能再上浮了 </span></span><br><span class="line">    <span class="keyword">while</span> (k &gt; <span class="number">1</span> &amp;&amp; less(parent(k), k)) &#123; </span><br><span class="line">        <span class="comment">// 如果第 k 个元素⽐上层⼤ </span></span><br><span class="line">        <span class="comment">// 将 k 换上去 </span></span><br><span class="line">        exch(parent(k), k); </span><br><span class="line">        k = parent(k); </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>下沉的代码实现：</strong> </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">sink</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123; </span><br><span class="line">    <span class="comment">// 如果沉到堆底，就沉不下去了 </span></span><br><span class="line">    <span class="keyword">while</span> (left(k) &lt;= N) &#123; </span><br><span class="line">        <span class="comment">// 先假设左边节点较⼤ </span></span><br><span class="line">        <span class="keyword">int</span> older = left(k); </span><br><span class="line">        <span class="comment">// 如果右边节点存在，⽐⼀下⼤⼩ </span></span><br><span class="line">        <span class="keyword">if</span> (right(k) &lt;= N &amp;&amp; less(older, right(k))) </span><br><span class="line">            older = right(k); </span><br><span class="line">        <span class="comment">// 结点 k ⽐俩孩⼦都⼤，就不必下沉了 </span></span><br><span class="line">        <span class="keyword">if</span> (less(older, k)) <span class="keyword">break</span>;</span><br><span class="line">        <span class="comment">// 否则，不符合最⼤堆的结构，下沉 k 结点 </span></span><br><span class="line">        exch(k, older); </span><br><span class="line">        k = older; </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>⾄此，⼆叉堆的主要操作就讲完了，⼀点都不难吧，代码加起来也就⼗⾏。 明⽩了 sink 和 swim 的⾏为，下⾯就可以实现优先级队列了</p>
<h2 id="实现-delMax-和-insert"><a href="#实现-delMax-和-insert" class="headerlink" title="实现 delMax 和 insert"></a><strong>实现</strong> <strong>delMax</strong> <strong>和</strong> <strong>insert</strong></h2><p>这两个⽅法就是建⽴在 swim 和 sink 上的。 <strong>insert</strong> <strong>⽅法先把要插⼊的元素添加到堆底的最后，然后让其上浮到正确位</strong> <strong>置。</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">insert</span><span class="params">(Key e)</span> </span>&#123; </span><br><span class="line">    N++; </span><br><span class="line">    <span class="comment">// 先把新元素加到最后 </span></span><br><span class="line">    pq[N] = e; </span><br><span class="line">    <span class="comment">// 然后让它上浮到正确的位置 </span></span><br><span class="line">    swim(N); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>delMax</strong> <strong>⽅法先把堆顶元素</strong> <strong>A</strong> <strong>和堆底最后的元素</strong> <strong>B</strong> <strong>对调，然后删除</strong> <strong>A****，最</strong> <strong>后让</strong> <strong>B</strong> <strong>下沉到正确位置。</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> Key <span class="title">delMax</span><span class="params">()</span> </span>&#123; </span><br><span class="line">    <span class="comment">// 最⼤堆的堆顶就是最⼤元素 </span></span><br><span class="line">    Key <span class="built_in">max</span> = pq[<span class="number">1</span>]; </span><br><span class="line">    <span class="comment">// 把这个最⼤元素换到最后，删除之 </span></span><br><span class="line">    exch(<span class="number">1</span>, N);</span><br><span class="line">    pq[N] = null; </span><br><span class="line">    N--; </span><br><span class="line">    <span class="comment">// 让 pq[1] 下沉到正确位置 </span></span><br><span class="line">    sink(<span class="number">1</span>); </span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">max</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>⾄此，⼀个优先级队列就实现了，插⼊和删除元素的时间复杂度为 O(logK) ， K 为当前⼆叉堆（优先级队列）中的元素总数。因为我们时间 复杂度主要花费在 sink 或者 swim 上，⽽不管上浮还是下沉，最多也就 树（堆）的⾼度，也就是 log 级别</p>
<h2 id="总结-1"><a href="#总结-1" class="headerlink" title="总结"></a>总结</h2><p>⼆叉堆就是⼀种完全⼆叉树，所以适合存储在数组中，⽽且⼆叉堆拥有⼀些 特殊性质。 </p>
<p>⼆叉堆的操作很简单，主要就是上浮和下沉，来维护堆的性质（堆有序）， 核⼼代码也就⼗⾏。 </p>
<p>优先级队列是基于⼆叉堆实现的，主要操作是插⼊和删除。插⼊是先插到最 后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位 置。核⼼代码也就⼗⾏。 </p>
<p>也许这就是数据结构的威⼒，简单的操作就能实现巧妙的功能，真⼼佩服发明⼆叉堆算法的⼈！ </p>
<h1 id=""><a href="#" class="headerlink" title=""></a></h1>
    </div>
    
    
    
    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
    
</div>

      
    </div>
        <div class="reward-container">
  <div>坚持原创技术分享，您的支持将鼓励我继续创作！</div>
  <button onclick="var qr = document.getElementById('qr'); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
      
      <div style="display: inline-block;">
        <img src="/images/alipay.png" alt="Li Yudong 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>Li Yudong
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://example.com/2020/10/08/%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/" title="数据结构算法">http://example.com/2020/10/08/算法/数据结构算法/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

    
      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95%E6%A1%86%E6%9E%B6/" rel="tag"># 算法框架</a>
          </div>
    
        

    
        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2020/09/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/" rel="prev" title="双指针查找与常用算法框架">
      <i class="fa fa-chevron-left"></i> 双指针查找与常用算法框架
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/01/09/%E5%89%8D%E7%AB%AF/DOM%E9%97%AE%E9%A2%98%E6%B1%87%E6%80%BB/" rel="next" title="DOM问题汇总">
      DOM问题汇总 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#二叉搜索树的操作集锦"><span class="nav-number">1.</span> <span class="nav-text">二叉搜索树的操作集锦</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#总路线"><span class="nav-number">1.1.</span> <span class="nav-text">总路线</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#如何把⼆叉树所有的节点中的值加⼀？"><span class="nav-number">1.1.1.</span> <span class="nav-text">如何把⼆叉树所有的节点中的值加⼀？</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#如何判断两棵⼆叉树是否完全相同？"><span class="nav-number">1.1.2.</span> <span class="nav-text">如何判断两棵⼆叉树是否完全相同？</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#判断BST的合法性"><span class="nav-number">1.2.</span> <span class="nav-text">判断BST的合法性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#在BST中查找一个数是否存在"><span class="nav-number">1.3.</span> <span class="nav-text">在BST中查找一个数是否存在</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#在-BST-中插⼊⼀个数"><span class="nav-number">1.4.</span> <span class="nav-text">在 BST 中插⼊⼀个数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#在-BST-中删除⼀个数"><span class="nav-number">1.5.</span> <span class="nav-text">在 BST 中删除⼀个数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#总结"><span class="nav-number">1.6.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#快速计算完全⼆叉树的节点"><span class="nav-number">2.</span> <span class="nav-text">快速计算完全⼆叉树的节点</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#具体方法"><span class="nav-number">2.1.</span> <span class="nav-text">具体方法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#复杂度分析"><span class="nav-number">2.2.</span> <span class="nav-text">复杂度分析</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#如何使用单调栈解题"><span class="nav-number">3.</span> <span class="nav-text">如何使用单调栈解题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#题目"><span class="nav-number">3.1.</span> <span class="nav-text">题目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#解法"><span class="nav-number">3.2.</span> <span class="nav-text">解法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#时间复杂度"><span class="nav-number">3.3.</span> <span class="nav-text">时间复杂度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#扩展问题：循环数组"><span class="nav-number">3.4.</span> <span class="nav-text">扩展问题：循环数组</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#利用单调队列解题"><span class="nav-number">4.</span> <span class="nav-text">利用单调队列解题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#题目-1"><span class="nav-number">4.1.</span> <span class="nav-text">题目</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二叉堆详解"><span class="nav-number">5.</span> <span class="nav-text">二叉堆详解</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#概述"><span class="nav-number">5.1.</span> <span class="nav-text">概述</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#优先级队列"><span class="nav-number">5.2.</span> <span class="nav-text">优先级队列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#swim和sink"><span class="nav-number">5.3.</span> <span class="nav-text">swim和sink</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现-delMax-和-insert"><span class="nav-number">5.4.</span> <span class="nav-text">实现 delMax 和 insert</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#总结-1"><span class="nav-number">5.5.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#"><span class="nav-number">6.</span> <span class="nav-text"></span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Li Yudong"
      src="/images/author.jpg">
  <p class="site-author-name" itemprop="name">Li Yudong</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">95</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">14</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">18</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/tiarmor1" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;tiarmor1" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:1157019137@qq.com" title="E-Mail → mailto:1157019137@qq.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2020 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Li Yudong</span>
</div>

        








      </div>
    </footer>
  </div>

  
  
  <script color='0,0,0' opacity='0.5' zIndex='-1' count='150' src="/lib1/canvas-nest/canvas-nest.min.js"></script>
  <script src="/lib1/anime.min.js"></script>
  <script src="/lib1/velocity/velocity.min.js"></script>
  <script src="/lib1/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  

  
   <canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
   <script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
   <script type="text/javascript" src="/js/fireworks.js"></script>
  
</body>
</html>

